An elliptic curve is a plane curve defined by an equation of the form:y2=x3+ax+b. The set of points on such a curve (i.e., all solutions of the equation together with a point at inanity) can be shown to form an abelian group with the point at infinity as the identity element. If the coordinates x and y are chosen from a finite field, the solutions form a finite abelian group. The discrete logarithm problem on such elliptic curve groups is believed to be more difficult than the corresponding problem in the multiplicative group of non-zero elements of the underlying finite field. Thus keys in elliptic curve cryptography can be chosen to be much shorter than RSA algorithm keys for a comparable level of security.
Due to the nature of the algorithms used in ECC-system, these systems are vulnerable to so-called side channel attacks which are based on analysis of the power consumption in the system. The most commonly used method is simple power analysis (SPA) in which an attacker needs only a single power trace from an execution of the scalar multiplication algorithm in the ECC-system to deduce the secret key. This is possible as the scalar multiplication algorithm processes the bits in the secret key one by one and consumes different amounts of power depending on whether the value of a given bit is 0 or 1.
An attacker analyzing the power consumption in an ECC-system will, therefore, see a trace 110 as shown in FIG. 1A. From the trace 110, the attacker can deduce that the bits of the secret key processed were 0001.
There exist various countermeasures against SPA, but all of these reduce the performance of the system to some extent. This is a major problem as performance is usually a major issue in cryptographic applications.
Among the known countermeasures, the method known as side channel atomicity results in the least performance penalty. Side channel atomicity was originally described in B. Chevallier-Mames, M. Ciet and M. Joye, “Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity” in IEEE Transactions on Computers, volume 53, 2004 (referred to herein as Chevallier-Mames et al). The basic idea of the countermeasure is to rewrite the scalar multiplication algorithm to make it appear as if it consisted of a sequence of identical blocks (“atoms”) with indistinguishable power traces. With side channel atomicity enabled an attacker will see a trace 120 as in FIG. 1B. No information about the secret key can be deduced from this trace 120.
There are, however, two serious problems with the known solution of side channel atomicity. First, the solution does not apply to high performance ECC-systems which make use of mixed coordinate representations of the curves being used. The solution only applies to situations where a fixed coordinate representation is used. As the use of mixed coordinate representations is necessary in highly optimized ECC-systems, this makes the solution of side channel atomicity less attractive. Second, the solution does not make use of the optimizations available for the curves recommended by NIST (see National Institute for Standards and Technology, “FIPS PUB 186-2”). This means that the solution introduces a higher performance penalty than necessary for the NIST curves. As these curves are described in open standards and are selected by the NSA for the Suite B algorithms (see National Security Agency, “Fact Sheet NSA Suite B Cryptography”, this is a major drawback for the solution of side channel atomicity.